package org.raymond.iworks.study.basic.structure.linkedlist;

import java.util.Stack;


public class SingleLinkedListTest {
    // 链表:线性结构,有序,
    // 1, 以节点的方式存储
    // 2, 每个节点包含data域,next域
    // 3, 各节点之间不一定连续(内存地址不一定连续)
    // 4, 链表分带头节点和不带头节点,可以根据需求来定
    // 头节点: 1),不存放具体的数据;2),作用就是表示单链表的头
    public static void main(String[] args) {
        linkedlistTest();
    }

    //
    public static void linkedlistTest(){
        /**
         * 创建
         * 1, 先创建一个head节点,作用就是表示单链表的头
         * 2, 每添加一个节点,就直接加入到链表的最后
         * 遍历:
         * 1, 通过一个辅助变量,帮助遍历整个单链表
         */
        HeroNode node1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode node2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode node3 = new HeroNode(3, "吴用", "智多星");
        HeroNode node4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode node5 = new HeroNode(5, "公孙胜", "入云龙");
        HeroNode node6 = new HeroNode(6, "关胜", "大刀");
        HeroNode node7 = new HeroNode(7, "秦明", "霹雳火");
        HeroNode node8 = new HeroNode(8, "呼延灼", "双鞭");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        /*
        singleLinkedList.add(node1);
        singleLinkedList.add(node2);
        singleLinkedList.add(node3);
        singleLinkedList.add(node4);
         */

        singleLinkedList.addByOrder(node7);
        singleLinkedList.addByOrder(node3);
        singleLinkedList.addByOrder(node5);
        singleLinkedList.addByOrder(node1);

        HeroNode head = singleLinkedList.head();

        System.out.println("all");
        singleLinkedList.list();

        /*
        HeroNode update2 = new HeroNode(1, "卢义", "火麒麟");
        singleLinkedList.update(update2);
        System.out.println("update");
        singleLinkedList.list();
        System.out.println("有效节点数: "+length(head));

        HeroNode del1 = new HeroNode(1, "", "");
        HeroNode del4 = new HeroNode(4, "", "");
        singleLinkedList.delete(del1);
        System.out.println("del1");
        singleLinkedList.list();
        System.out.println("有效节点数: "+length(head));

        singleLinkedList.delete(del4);
        System.out.println("del4");
        singleLinkedList.list();
        System.out.println("有效节点数: "+length(head));

        singleLinkedList.addByOrder(node1);
        singleLinkedList.addByOrder(node4);

        HeroNode last1 = findLastIndexNode(head, 1);
        System.out.println("倒数第1个元素: "+last1);

        HeroNode last3 = findLastIndexNode(head, 3);
        System.out.println("倒数第3个元素: "+last3);

        HeroNode last4 = findLastIndexNode(head, 4);
        System.out.println("倒数第4个元素: "+last4);
         */

        //reverseList(head);
        //singleLinkedList.list();

        System.out.println("逆序打印,不改链表结构");
        reverseLog2(head);
        System.out.println("打印链表,验证结构是否改变");
        singleLinkedList.list();


        SingleLinkedList list2 = new SingleLinkedList();
        list2.addByOrder(node8);
        //list2.addByOrder(node2);
        list2.addByOrder(node4);
        list2.addByOrder(node6);

        System.out.println("list1");
        singleLinkedList.list();
        System.out.println("list2");
        list2.list();
        //SingleLinkedList merged = mergeOrder(head, list2.head());
        //System.out.println("合并结果");
        //merged.list();

        SingleLinkedList merged2 = mergeOrder2(head, list2.head());
        System.out.println("合并结果");
        merged2.list();
    }

    // 获取单链表的节点数,如果带头节点,不统计头节点
    public static int length(HeroNode head){
        if(head.next==null){
            return 0;
        }
        int length = 0;
        // 此处忽略头节点
        HeroNode cur = head.next;
        while(cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    /**
     * 查找单链表中倒数第k个节点
     * 思路:
     * 1, 编写一个方法,接收head节点,同时接收一个index
     * 2, index表示是倒数第index个节点
     * 3, 获取有效节点数length
     * 4, 从链表的第一个开始遍历(length-index)个
     * 5, 如果找到了,返回该节点,否则返回Null
     */
    public static HeroNode findLastIndexNode(HeroNode head, int idx){
        if(head.next==null) return null;

        int size = length(head);
        // 第二次遍历到size-idx位置,即倒数第k个节点
        // 先校验, idx应该小于等于size
        if(idx<=0 || idx>size) return null;

        // 忽略head节点
        HeroNode cur = head.next;
        for(int i=0; i<size-idx; i++){
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 反转单链表
     * head->1->2->3
     * 1->null
     * reverse->1
     * 2->1
     * reverse->2->1
     * 3->2
     * reverse->3->2->1
     * head->3->2->1
     * @param head
     */
    public static void reverseList(HeroNode head){
        if(head.next==null || head.next.next==null){
            return;
        }
        // 指向当前节点
        HeroNode cur = head.next;
        // 指向当前节点的下一个节点
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0, "", "");
        // 遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead的最前端
        while(cur!=null){
            next = cur.next;
            // 将cur的下一个节点指向新的链表的最前端
            cur.next=reverseHead.next;
            // 使新的链表的最前端指向cur,即将cur
            reverseHead.next=cur;
            // 让cur后移
            cur = next;
        }
        head.next=reverseHead.next;
    }

    /**
     * 从尾到头打印单链表
     * 要求方式:1,反向遍历.2,Stack栈
     *
     * 方案1:先反转,再遍历打印. 存在问题:反转会修改链表结构,不完全符合题目要求,且会耗费更多内存空间
     * 方案2:利用stack,将各节点压入栈中,出栈时自然逆序,FILO
     */
    public static void reverseLog2(HeroNode head){
        if(head.next==null){
            return;
        }
        // 创建一个栈,将各个节点压入栈中
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        while (cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.empty()){
            System.out.println(stack.pop());
        }
    }

    // 合并两个有序链表,要求合并后依然是有序的
    /**
     * 思路分析:
     * 1, 新建链表
     * 2, 遍历head1,将head1的节点逐个按序加入新的链表中
     * 3, 遍历head2,将head2的节点逐个按序加入新的链表中
     * 4, 按no从小到大排序
     * head1->1->3->5->7
     * head2->2->4->6->8
     * master->1->2->3->4->5->6->7->8
     */
    public static SingleLinkedList mergeOrder(HeroNode head1, HeroNode head2){
        SingleLinkedList mergedList = new SingleLinkedList();

        HeroNode cur = head1.next;
        HeroNode next = null;
        while(cur!=null){
            next = cur.next;
            mergedList.addByOrder(cur);
            cur = next;
        }
        cur = head2.next;
        while(cur!=null){
            next = cur.next;
            mergedList.addByOrder(cur);
            cur = next;
        }
        return mergedList;
    }

    /**
     * 合并有序列表,思路来自merge-sort
     */
    public static SingleLinkedList mergeOrder2(HeroNode head1, HeroNode head2){
        SingleLinkedList mergedList = new SingleLinkedList();

        HeroNode i = head1.next;
        HeroNode j = head2.next;
        while(i!=null){
            while(j!=null){
                if(j.no<i.no){
                    mergedList.add(j);
                }else{
                    mergedList.add(i);
                    break;
                }
                j = j.next;
            }
            i = i.next;
        }
        return mergedList;
    }
}
